#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_TREE_SIZE 100 // 树的最大结点数

// 孩子结点（链表结构）
typedef struct ChildNode
{
    int childIndex;         // 孩子在数组中的下标
    struct ChildNode *next; // 指向下一个孩子的指针
} ChildNode;

// 树结点结构（顺序存储）
typedef struct
{
    int data;              // 结点数据
    ChildNode *firstChild; // 指向第一个孩子的指针
} CTNode;

// 树结构
typedef struct
{
    CTNode nodes[MAX_TREE_SIZE]; // 结点数组
    int rootIndex;               // 根结点下标（-1表示空树）
    int nodeCount;               // 当前结点数
} CTree;

// 1. 初始化树（创建空树）
void InitTree(CTree &T)
{
    T.rootIndex = -1; // 根结点置为-1
    T.nodeCount = 0;  // 结点数置0
    for (int i = 0; i < MAX_TREE_SIZE; i++)
    {
        T.nodes[i].data = -1;         // 数据置为-1（无效值）
        T.nodes[i].firstChild = NULL; // 孩子指针置空
    }
}

// 2. 销毁树（释放所有资源）
void DestroyTree(CTree &T)
{
    // 释放所有孩子链表
    for (int i = 0; i < MAX_TREE_SIZE; i++)
    {
        ChildNode *p = T.nodes[i].firstChild;
        while (p != NULL)
        {
            ChildNode *temp = p;
            p = p->next;
            free(temp);
        }
        T.nodes[i].firstChild = NULL;
    }
    T.rootIndex = -1; // 重置根结点
    T.nodeCount = 0;  // 重置结点数
}

// 辅助函数：查找父结点下标
int FindParentIndex(CTree T, int childIndex)
{
    for (int i = 0; i < MAX_TREE_SIZE; i++)
    {
        if (T.nodes[i].data != -1)
        { // 跳过空结点
            ChildNode *p = T.nodes[i].firstChild;
            while (p != NULL)
            {
                if (p->childIndex == childIndex)
                {
                    return i; // 找到父结点
                }
                p = p->next;
            }
        }
    }
    return -1; // 未找到父结点
}

// 3. 插入结点
bool InsertNode(CTree &T, int value, int parentIndex, bool isFirstChild)
{
    // 查找可用位置
    int newIndex = -1;
    for (int i = 0; i < MAX_TREE_SIZE; i++)
    {
        if (T.nodes[i].data == -1)
        {
            newIndex = i;
            break;
        }
    }
    if (newIndex == -1)
    {
        printf("Error: Tree is full\n");
        return false; // 树已满
    }

    // 设置新结点数据
    T.nodes[newIndex].data = value;

    // 处理根结点
    if (parentIndex == -1)
    {
        if (T.rootIndex != -1)
        {
            printf("Error: Root already exists\n");
            T.nodes[newIndex].data = -1; // 恢复状态
            return false;
        }
        T.rootIndex = newIndex;
        T.nodeCount++;
        return true;
    }

    // 检查父结点有效性
    if (parentIndex < 0 || parentIndex >= MAX_TREE_SIZE || T.nodes[parentIndex].data == -1)
    {
        printf("Error: Invalid parent node\n");
        T.nodes[newIndex].data = -1;
        return false;
    }

    // 检查孩子数量（最多3个）
    int childCount = 0;
    ChildNode *p = T.nodes[parentIndex].firstChild;
    while (p != NULL)
    {
        childCount++;
        p = p->next;
    }
    if (childCount >= 3)
    {
        printf("Error: Parent node already has 3 children\n");
        T.nodes[newIndex].data = -1;
        return false;
    }

    // 创建新孩子结点
    ChildNode *newChild = (ChildNode *)malloc(sizeof(ChildNode));
    if (!newChild)
    {
        printf("Error: Memory allocation failed\n");
        T.nodes[newIndex].data = -1;
        return false;
    }
    newChild->childIndex = newIndex;
    newChild->next = NULL;

    // 插入到孩子链表
    if (T.nodes[parentIndex].firstChild == NULL || isFirstChild)
    {
        // 插入到链表头部
        newChild->next = T.nodes[parentIndex].firstChild;
        T.nodes[parentIndex].firstChild = newChild;
    }
    else
    {
        // 插入到链表尾部
        ChildNode *last = T.nodes[parentIndex].firstChild;
        while (last->next != NULL)
        {
            last = last->next;
        }
        last->next = newChild;
    }

    T.nodeCount++;
    return true;
}

// 4. 删除结点（递归删除子树）
void DeleteSubTree(CTree &T, int index)
{
    if (index < 0 || index >= MAX_TREE_SIZE || T.nodes[index].data == -1)
    {
        return; // 无效结点
    }

    // 递归删除所有孩子
    ChildNode *p = T.nodes[index].firstChild;
    while (p != NULL)
    {
        DeleteSubTree(T, p->childIndex); // 递归删除子树
        ChildNode *temp = p;
        p = p->next;
        free(temp); // 释放孩子结点
    }
    T.nodes[index].firstChild = NULL;
    T.nodes[index].data = -1; // 标记为空
    T.nodeCount--;
}

bool DeleteNode(CTree &T, int value)
{
    int index = -1;
    // 查找目标结点
    for (int i = 0; i < MAX_TREE_SIZE; i++)
    {
        if (T.nodes[i].data == value)
        {
            index = i;
            break;
        }
    }
    if (index == -1)
    {
        printf("Error: Node not found\n");
        return false; // 结点不存在
    }

    // 处理根结点
    if (index == T.rootIndex)
    {
        DeleteSubTree(T, index);
        T.rootIndex = -1;
        return true;
    }

    // 查找父结点
    int parentIndex = FindParentIndex(T, index);
    if (parentIndex == -1)
    {
        printf("Error: Parent node not found\n");
        return false;
    }

    // 从父结点的孩子链表中移除
    ChildNode *prev = NULL;
    ChildNode *curr = T.nodes[parentIndex].firstChild;
    while (curr != NULL)
    {
        if (curr->childIndex == index)
        {
            if (prev == NULL)
            {
                T.nodes[parentIndex].firstChild = curr->next;
            }
            else
            {
                prev->next = curr->next;
            }
            free(curr);
            break;
        }
        prev = curr;
        curr = curr->next;
    }

    // 删除子树
    DeleteSubTree(T, index);
    return true;
}

// 5.1 先根遍历
void PreOrder(CTree T, int index)
{
    if (index < 0 || index >= MAX_TREE_SIZE || T.nodes[index].data == -1)
    {
        return;
    }
    printf("%d ", T.nodes[index].data); // 访问当前结点

    // 遍历所有孩子
    ChildNode *p = T.nodes[index].firstChild;
    while (p != NULL)
    {
        PreOrder(T, p->childIndex);
        p = p->next;
    }
}

// 5.2 后根遍历
void PostOrder(CTree T, int index)
{
    if (index < 0 || index >= MAX_TREE_SIZE || T.nodes[index].data == -1)
    {
        return;
    }

    // 先遍历所有孩子
    ChildNode *p = T.nodes[index].firstChild;
    while (p != NULL)
    {
        PostOrder(T, p->childIndex);
        p = p->next;
    }

    printf("%d ", T.nodes[index].data); // 最后访问当前结点
}

// 5.3 层序遍历
void LevelOrder(CTree T)
{
    if (T.rootIndex == -1)
        return;

    int queue[MAX_TREE_SIZE];
    int front = 0, rear = 0;

    // 根结点入队
    queue[rear++] = T.rootIndex;

    while (front < rear)
    {
        int index = queue[front++];
        printf("%d ", T.nodes[index].data); // 访问结点

        // 所有孩子入队
        ChildNode *p = T.nodes[index].firstChild;
        while (p != NULL)
        {
            queue[rear++] = p->childIndex;
            p = p->next;
        }
    }
}

// 5. 遍历树（选择不同遍历方式）
void Traversal(CTree T, const char *order)
{
    if (T.rootIndex == -1)
    {
        printf("Tree is empty\n");
        return;
    }

    if (strcmp(order, "preorder") == 0)
    {
        PreOrder(T, T.rootIndex);
    }
    else if (strcmp(order, "postorder") == 0)
    {
        PostOrder(T, T.rootIndex);
    }
    else if (strcmp(order, "levelorder") == 0)
    {
        LevelOrder(T);
    }
    printf("\n");
}

// 6. 查找结点（返回数组下标）
int Search(CTree T, int value)
{
    for (int i = 0; i < MAX_TREE_SIZE; i++)
    {
        if (T.nodes[i].data == value)
        {
            return i; // 返回下标
        }
    }
    return -1; // 未找到
}

// 7. 判空树
bool TreeEmpty(CTree T)
{
    return (T.rootIndex == -1);
}

// 8. 获取树深度
int TreeDepth(CTree T, int index)
{
    if (index < 0 || index >= MAX_TREE_SIZE || T.nodes[index].data == -1)
    {
        return 0;
    }

    int maxDepth = 0;
    ChildNode *p = T.nodes[index].firstChild;
    while (p != NULL)
    {
        int depth = TreeDepth(T, p->childIndex);
        if (depth > maxDepth)
        {
            maxDepth = depth;
        }
        p = p->next;
    }
    return maxDepth + 1;
}

int GetTreeDepth(CTree T)
{
    if (T.rootIndex == -1)
        return 0;
    return TreeDepth(T, T.rootIndex);
}

int main()
{
    CTree T;
    InitTree(T);

    // 插入根结点
    printf("Insert root node 1: %s\n", InsertNode(T, 1, -1, true) ? "Success" : "Fail");
    printf("Is tree empty? %s\n", TreeEmpty(T) ? "Yes" : "No");

    // 插入其他结点
    int rootIndex = T.rootIndex;
    printf("Insert node 2 as first child of 1: %s\n", InsertNode(T, 2, rootIndex, true) ? "Success" : "Fail");
    printf("Insert node 3 as second child of 1: %s\n", InsertNode(T, 3, rootIndex, false) ? "Success" : "Fail");
    printf("Insert node 4 as first child of 2: %s\n", InsertNode(T, 4, Search(T, 2), true) ? "Success" : "Fail");
    printf("Insert node 5 as second child of 2: %s\n", InsertNode(T, 5, Search(T, 2), false) ? "Success" : "Fail");
    printf("Insert node 6 as first child of 3: %s\n", InsertNode(T, 6, Search(T, 3), true) ? "Success" : "Fail");

    // 获取深度
    printf("Tree depth: %d\n", GetTreeDepth(T));

    // 遍历测试
    printf("Preorder traversal: ");
    Traversal(T, "preorder");

    printf("Postorder traversal: ");
    Traversal(T, "postorder");

    printf("Levelorder traversal: ");
    Traversal(T, "levelorder");

    // 删除结点测试
    printf("Delete node 2 and its subtree: %s\n", DeleteNode(T, 2) ? "Success" : "Fail");
    printf("Levelorder traversal after deletion: ");
    Traversal(T, "levelorder");
    printf("Tree depth after deletion: %d\n", GetTreeDepth(T));

    // 销毁树
    DestroyTree(T);
    printf("After destroying tree, is empty? %s\n", TreeEmpty(T) ? "Yes" : "No");

    return 0;
}